package Arithmetic;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 34255
 * Date: 2024-11-08
 * Time: 11:51
 */
//前缀和
public class PrefixSum {
    public static Scanner scanner = new Scanner(System.in);

    //DP34 前缀和-牛客

    /**
     * 时间复杂度：O(len) + O(num)
     * 空间复杂度：O(1)
     */
    public static void oneArrPrefixSum() {
        int len = scanner.nextInt();
        int num = scanner.nextInt();
        int[] prefixSum = new int[len + 1];
        //读取数组内容
        for(int i = 1;i <= len;i++) prefixSum[i] = scanner.nextInt();

        //1.创建前缀和数组
        long[] dp = new long[len + 1];//防止溢出
        for(int i = 1;i <= len;i++) dp[i] = dp[i - 1] + prefixSum[i];

        //2.使用前缀和数组
        while(num != 0){
            int left = scanner.nextInt();
            int right = scanner.nextInt();
            System.out.println(dp[right] - dp[left - 1]);
            num--;
        }
    }

    //DP35 二维前缀和-牛客

    /**
     * 时间复杂度：O(n * m) + O(q)
     * 空间复杂度：O(1)
     */
    public static void twoArrPrefixSum() {
        int row = scanner.nextInt();
        int col = scanner.nextInt();

        int queryCount = scanner.nextInt();
        int[][] array = new int[row + 1][col + 1];

        //读取数组内容
        for(int i = 1;i <= row;i++){
            for(int j = 1;j <= col;j++){
                array[i][j] = scanner.nextInt();
            }
        }

        //1.创建前缀和数组
        long[][] Dp = new long[row + 1][col + 1];//防止溢出
        for(int i = 1;i <= row;i++){
            for(int j = 1;j <= col;j++){
                Dp[i][j] = Dp[i - 1][j] + Dp[i][j - 1] + array[i][j] - Dp[i - 1][j - 1];
            }
        }

        //使用前缀和数组
        while(queryCount != 0){
            int x1 = scanner.nextInt();
            int y1 = scanner.nextInt();
            int x2 = scanner.nextInt();
            int y2 = scanner.nextInt();
            System.out.println(Dp[x2][y2] - Dp[x2][y1 - 1] - Dp[x1 - 1][y2] + Dp[x1 - 1][y1 - 1]);
            queryCount--;
        }
    }

    //724.寻找数组中心下标

    /**
     * 时间复杂度：O(N)
     * 空间复杂度：O(N)
     * @param nums 数组
     * @return 中心下标
     */
    public static int pivotIndex(int[] nums) {
        //创建前缀和数组
        int[] DP = new int[nums.length];
        for(int i = 0;i < DP.length;i++){
            if(i == 0) DP[i] = nums[i];
            else DP[i] = DP[i - 1] + nums[i];
        }

        //使用前缀和数组
        //这样会漏掉下标0为中心下标的情况，虽然保证了数组不会越界访问
        for(int i = 0;i < DP.length;i++){
            if(i != 0 && DP[i] == DP[DP.length - 1] - DP[i - 1]){
                return i;//代表当前下标就是中心下标
            }else if(DP[DP.length - 1] - DP[0] == 0){//0的情况特殊处理
                return 0;
            }
        }
        return -1;
    }

    //238.除自身以外数组的乘积

    /**
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * @param nums
     * @return
     */
    public static int[] productExceptSelf(int[] nums) {
        //预处理后缀积数组
        int[] g = new int[nums.length];
        for(int i = nums.length - 1;i >= 0;i--){
            if(i != nums.length - 1) g[i] = g[i + 1] * nums[i + 1];
            else g[i] = 1;
        }
        //使用前缀积和后缀积数组
        int product = nums[0];//存储前缀和乘积
        for(int i = 0;i < nums.length;i++){
            if(i > 0){
                int temp = g[i];
                g[i] = g[i] * product;
                product *= temp;
            }
        }
        return g;
    }

    //560.和为K的子数组

    /**
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * @param nums
     * @param k
     * @return 子数组个数
     */
    public static int subarraySum(int[] nums, int k) {
        int cnt = 0;

        //预处理前缀和数组
        int[] sum = new int[nums.length];
        for(int i = 0;i < nums.length;i++){
            if(i == 0) sum[0] = nums[0];
            else sum[i] = sum[i - 1] + nums[i];
        }

        //key:sum[i] - K value:出现次数
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,1);//防止sum[i]刚好等于零的情况

        for(int i = 0;i < sum.length;i++){
            //统计[0,i-1]区间sum[i]-k次数
            cnt += map.getOrDefault(sum[i] - k,0);
            map.put(sum[i],map.getOrDefault(sum[i],0) + 1);
        }
        return cnt;
    }

    public static void main(String[] args) {
        //DP34 前缀和-牛客
//        oneArrPrefixSum();

        //DP35 二维前缀和-牛客
//        twoArrPrefixSum();

        //724.寻找数组中心下标
        int[] array1 = {-1,-1,0,1,1,0};
        int index = pivotIndex(array1);
        System.out.println(index);

        //238.除自身以外数组的乘积
        int[] array2 = {1,2,3,4};
        int[] ans = productExceptSelf(array2);
        System.out.println(Arrays.toString(ans));

        //560.和为K的子数组
        int[] array3 = {1,2,3};
        int cnt = subarraySum(array3,3);
        System.out.println(cnt);

    }
}
